package site.wanjiahao.back_tracking;

/**
 * N皇后问题
 * 使用回溯＋剪枝处理
 *      使用位运算优化，只能使用位数相对而言比较少的
 */
public class Queens3 {

    // 标记某一列是否有换后
    private byte cols;

    // 标记左上斜对角线
    private short leftTop;

    // 标记右上斜对角线
    private short rightTop;

    private int ways;


    // 摆放皇后
    public void place() {
        // 从第一个元素开始摆放
        place(0);
        System.out.println("共有" + ways + "种摆法");
    }

    public void place(int row) {
        // 确定递归基
        if (row >= 8) {
            // 成功确定一次摆放位置
            ways++;
            // 展示当前摆放，详情
            return;
        }
        // 遍历列，确定那个位置摆放皇后
        for (int col = 0; col < 8; col++) {
            // 列不能摆放
            int colV = 1 << col;
            if ((cols & colV) != 0) continue;
            // 对角线不能摆放
            int ltV = (1 << (row - col + 7));
            if ((leftTop & ltV) != 0) continue;
            int rtV = (1 << (row + col));
            if ((rightTop & rtV) != 0) continue;

            cols |= colV;
            leftTop |= ltV;
            rightTop |= rtV;
            // 递归调用下一个元素摆放，当此函数弹出，将会自动执行回溯操作
            place(row + 1);
            cols &= ~colV;
            leftTop &= ~ltV;
            rightTop &= ~rtV;
        }
    }
}
